package com.tree;


import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;
import jdk.nashorn.internal.ir.IfNode;
import jdk.nashorn.internal.ir.LabelNode;

import java.util.*;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: BinarytreeDemo
 * @description: 二叉树
 * @date 2021/3/514:41
 * @since V1.0
 */
public class BinarytreeDemo {

    public static void main(String[] args) {
        HeroNode a = new HeroNode(1, "A");
        HeroNode b = new HeroNode(2, "B");
        a.leftNode = b;
        HeroNode c = new HeroNode(3, "C");
        b.leftNode = c;
        HeroNode d = new HeroNode(4, "D");
        c.leftNode = d;
        HeroNode e = new HeroNode(5, "E");
        c.rightNode = e;
        HeroNode f = new HeroNode(6, "F");
        a.rightNode = f;
        HeroNode g = new HeroNode(7, "G");
        f.leftNode = g;
        HeroNode h = new HeroNode(8, "H");
        f.rightNode = h;
        HeroNode i = new HeroNode(9, "I");
        h.rightNode = i;
        HeroNode j = new HeroNode(10, "J");
        i.leftNode = j;
        HeroNode k = new HeroNode(11, "K");
        i.rightNode = k;
        MyBinarytree myBinarytree = new MyBinarytree(a);
//        System.out.println("前序");
//        myBinarytree.preOrder();
        System.out.println("中序");
        myBinarytree.infixOrder();
        System.out.println("中序2");
        myBinarytree.infixOrder2();
//        System.out.println("后序");
//        myBinarytree.postOrder();
//        System.out.println(myBinarytree.preFind(221));
//        System.out.println(myBinarytree.delete(1));
//        myBinarytree.preOrder();
    }
}
class MyBinarytree{
    public HeroNode head;

    public MyBinarytree(){

    }

    public MyBinarytree(HeroNode heroNode){
        head = heroNode;
    }

    public void preOrder(){
        if (head==null){
            System.out.println("二叉树内无元素");
            return;
        }
        head.preOrder();
    }
    public void infixOrder(){
        head.infixOrder();
    }

    public void infixOrder2(){
        head.infixOrder2();
    }
    public void postOrder(){
        head.postOrder();
    }
    public HeroNode preFind(int num){
        return head.preFind(num);
    }
    public boolean delete(int num){
        boolean res = true;
        if (head.getId()==num){
            head = null;
        }else {
            res = head.delete(num);
        }
        return res;

    }
}

class HeroNode{
    private int id;
    private String name;
    public HeroNode leftNode;
    public HeroNode rightNode;

    public HeroNode(int i, String a) {
        id=i;
        name = a;
    }

    public HeroNode() {

    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }


    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    //前序遍历
   public void preOrder(){
       System.out.println(this);
       if (this.leftNode!=null) this.leftNode.preOrder();
       if (this.rightNode!=null) this.rightNode.preOrder();
   }

    //前序遍历-非递归
    public void preOrder2(){
        Deque<HeroNode> dq = new LinkedList<>();
        HeroNode p = this;
        while (p!=null || !dq.isEmpty()){
            if (p!=null){
                System.out.println(p);
                dq.push(p);
                p = p.leftNode;
            }else {
                HeroNode pop = dq.pop();
                p = pop.rightNode;
            }
        }
    }
    //中序遍历
    public void infixOrder(){
        if (this.leftNode!=null) this.leftNode.infixOrder();
        System.out.println(this);
        if (this.rightNode!=null) this.rightNode.infixOrder();
    }

    //中序遍历-非递归
    public void infixOrder2(){
        Deque<HeroNode> dq = new LinkedList<>();
        HeroNode p = this;
        while (p!=null || !dq.isEmpty()){
            if (p!=null){
                dq.push(p);
                p = p.leftNode;
            }else {
                HeroNode pop = dq.pop();
                System.out.println(pop);
                p = pop.rightNode;
            }
        }
    }
    //后序遍历
    public void postOrder(){
        if (this.leftNode!=null) this.leftNode.postOrder();
        if (this.rightNode!=null) this.rightNode.postOrder();
        System.out.println(this);
    }

    //后序遍历-非递归
    public void postOrder2(){
        Stack<HeroNode> q1 = new Stack();
        Map<Integer,Integer > map=new HashMap<>();
        HeroNode t = this;
        while(!q1.isEmpty()||t!=null)
        {
            if (t!=null) {
                q1.push(t);
                map.put(t.id, 1); //t.value标记这个值节点出现的次数
                t=t.leftNode;
            }
            else {
                t=q1.peek();
                if(map.get(t.id)==2) {//第二次访问，抛出
                    q1.pop();
                    System.out.print(t);
                    t=null;//需要往上走
                }
                else {
                    map.put(t.id, 2);
                    t=t.rightNode;
                }
            }
        }
    }

    //前序查找
    public HeroNode preFind(int num){
        HeroNode res = null;
        if (this.id == num){
            return this;
        }
        if (this.leftNode!=null){
            res = this.leftNode.preFind(num);
        }
        if (res ==null && this.rightNode!=null){
            res = this.rightNode.preFind(num);
        }
        return res;
    }
    //前序删除
    public boolean delete(int id){
        if (this.leftNode!=null && this.leftNode.id==id){
            this.leftNode = null;
            return true;
        }
        if (this.rightNode!=null && this.rightNode.id==id){
            this.rightNode = null;
            return true;
        }
        boolean flag=false;
        if (this.leftNode!=null){
            flag =  this.leftNode.delete(id);
        }
        if (this.rightNode!=null && flag==false){
            flag = this.rightNode.delete(id);
        }
        return flag;
    }

}